package util

import (
	"fmt"
)

// 链表结点
type LinkListNode struct {
	Value interface{}
	Next  *LinkListNode
}

// 单链表
type SingleLinkList struct {
	Lenght   int
	HeadNode *LinkListNode
}

// 初始化链表结点
func NewLinkListNode(value interface{}) *LinkListNode {
	return &LinkListNode{
		Value: value,
	}
}

// 初始化链表
func NewSingleLinkList() *SingleLinkList {
	return &SingleLinkList{
		HeadNode: new(LinkListNode),
	}
}

// 头插法
func (singleLinkList *SingleLinkList) AddLinkNode(value interface{}) {
	node := NewLinkListNode(value)
	if singleLinkList.IsNull() {
		singleLinkList.HeadNode = node
		singleLinkList.Lenght++
		return
	}
	// 将链表头结点给到结点的下个结点
	node.Next = singleLinkList.HeadNode
	// 将链表头结点改为当前结点
	singleLinkList.HeadNode = node
	singleLinkList.Lenght++
}

// 尾插法
func (singleLinkList *SingleLinkList) AppendLinkNode(value interface{}) {
	node := NewLinkListNode(value)
	if singleLinkList.IsNull() {
		singleLinkList.HeadNode.Next = node
	} else {
		// 获取当前头结点
		current := singleLinkList.HeadNode
		// 一直循环获取链表的最后一个结点
		for current.Next != nil {
			current = current.Next
		}
		// 获取到最后一个结点后给它的下一个一个结点赋值
		current.Next = node
	}
	singleLinkList.Lenght++
}

// 判断链表是否为空
func (singleLinkList *SingleLinkList) IsNull() bool {
	if singleLinkList.Lenght == 0 {
		return true
	} else {
		return false
	}
}

// 显示链表
func (singleLinkList *SingleLinkList) ShowSingleLinkList() {
	if !singleLinkList.IsNull() {
		// 获取头结点
		current := singleLinkList.HeadNode
		for {
			// 一直循环输出结点值
			fmt.Printf("\t%v", current.Value)
			if current.Next != nil {
				current = current.Next
			} else {
				break
			}
		}
		fmt.Println()
	}
}

// 第一种反转链表
func (singleLinkList *SingleLinkList) ReverseSingleLinkList() {
	if singleLinkList.IsNull() {
		return
	}
	// 获取头结点
	current := singleLinkList.HeadNode
	// 前一个结点
	var preNode *LinkListNode
	// 反转头结点
	var reverseHead *LinkListNode
	for current != nil {
		// 将当前结点的下一个结点存储
		nextNode := current.Next
		if nextNode == nil {
			// 如果没有下一个结点就将当前结点赋值给反转结点
			reverseHead = current
		}
		// 将前一个结点赋给当前节点的下一个结点
		current.Next = preNode
		preNode = current
		current = nextNode
	}
	singleLinkList.HeadNode = reverseHead
}

// 第二种反转链表
func ReverseSingleLinkList(singleLinkList *SingleLinkList) (result *SingleLinkList) {
	list := NewSingleLinkList()
	if singleLinkList.IsNull() {
		return list
	}
	current := singleLinkList.HeadNode
	for {
		list.AddLinkNode(current.Value)
		if current.Next != nil {
			current = current.Next
		} else {
			break
		}
	}
	return list
}
